import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];//创建一个数组
    }

    //建堆，按照大根堆来建立
    public void creativeHeap(int[] array) {
        for (int i = 0; i < array.length; ++i) {
            this.elem[i] = array[i];
            this.usedSize++;
        }

        for (int p = (this.usedSize - 1 - 1) / 2; p >= 0; p--) {
            shiftDown(p, this.usedSize);
        }

    }

    public void shiftDown(int root, int len) {
        int parent = root;
        int child = 2 * parent + 1;//跟的左孩子
        while (child < len) {
            //找到孩子节点最大的
            if (child + 1 < len && this.elem[child] < this.elem[child + 1]) {
                child++;
            }
            //此时child是最大的，孩子最大的要与parent交换
            if (this.elem[parent] < this.elem[child]) {
                //如果父母比孩子小那就交换
                swap(this.elem, child, parent);
                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    public void swap(int[] elem, int i, int j) {
        int tmp = this.elem[i];
        this.elem[i] = this.elem[j];
        this.elem[j] = tmp;
    }

    private boolean isFull(){
        return this.usedSize==this.elem.length;
    }

    //堆的插入和删除
    public void push(int val){
        //如果满了插入就需要增容
        if(isFull()){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        //不满就需要插入了
        this.elem[usedSize] = val;
        //从新插入以后还要继续调堆-->错误
      ///  shiftUp(this.usedSize);
        this.usedSize++;
    }
//
//    //向上调整
//    public void shiftUp(int root){
//       int parent = root;
//       int child = 2*parent+1;
//       while(child>=0){
//           if(child+1< this.elem.length&&this.elem[child]<this.elem[child+1]){
//               child++;
//           }
//           if(this.elem[parent]<this.elem[child]) {
//               swap(this.elem, child, parent);
//               child = parent;
//               parent = (child-1)/2;
//           }else {
//               break;
//           }
//       }
//    }


    public boolean isEmpty(){
      return this.usedSize==0;
    }

    //堆的删除-->删除元素同时也要调整堆
    //其中堆删除的一定是堆顶元素
    public void remove(){
        //删除思路，将堆顶元素与最后的元素交换，然后有效个数-1
        //其中如果数组为空，那就不能进行删除操作
        if(isEmpty()){
            return;
        }
        //数组不为空我们就进行删除操作
        //首先让堆顶元素与末尾元素进行交换
        swap(elem,0,this.usedSize-1);
        this.usedSize--;
        //错误
        for (int p = (this.usedSize - 1 - 1) / 2; p >= 0; p--) {
            shiftDown(p, this.usedSize);
        }
    }



}

